package org.example.greedy;

import java.util.*;

/**
 * 贪心算法
 * @Author chaigq
 * @Date 2020/9/9 9:15 上午
 * @Version 1.0
 */
public class LeetCodeGreedy {

    /**
     * 贪心算法的基本要素：
     *
     * 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，
     * 也是贪心算法与动态规划算法的主要区别。
     *
     * 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
     *
     * 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
     *
     * 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
     *
     * 贪心算法的基本思路：
     *
     * 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。
     *
     * 该算法存在问题：
     *
     * 1. 不能保证求得的最后解是最佳的；
     *
     * 2. 不能用来求最大或最小解问题；
     *
     * 3. 只能求满足某些约束条件的可行解的范围。
     *
     * 实现该算法的过程：
     *
     * 从问题的某一初始解出发；
     *
     * while 能朝给定总目标前进一步 do
     *
     * 　　 求出可行解的一个解元素；
     *
     * 由所有解元素组合成问题的一个可行解；
     */

    /**
     * 1、键键盘
     * 假设你有一个特殊的键盘包含下面的按键：
     *
     * Key 1: (A)：在屏幕上打印一个 'A'。
     *
     * Key 2: (Ctrl-A)：选中整个屏幕。
     *
     * Key 3: (Ctrl-C)：复制选中区域到缓冲区。
     *
     * Key 4: (Ctrl-V)：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。
     *
     * 现在，你只可以按键 N 次（使用上述四种按键），请问屏幕上最多可以显示几个 'A'呢？
     *
     */
    public static int maxA(int N) {
        // 定义数组
        int[] a_num = new int[N + 1];
        a_num[0] = 0;
        // 循环遍历N次数
        for (int i = 1;i <= N; i ++){
            // 选择按A
            a_num[i] = a_num[i-1] + 1;
            // 选择按V
            for (int j = 0; j <= i-2; j ++ ){
                // 计算按V的数量,N = 按v之前的数 + V的次数 * 按V之前的数
                // i-2表示第i次之前按下了Ctrl + A 和 Ctrl + C 两次操作
                // i-2-j 表示按v的次数
                // a_num[i] = a_num[j] + a_num[j]*(i-2-j);
                a_num[i] = Math.max(a_num[i],a_num[j]*(i-1-j));
            }
        }
        return a_num[N];
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }

    public int[] advantageCount(int[] A, int[] B) {
        Arrays.sort(A);
        List<Integer> list = new ArrayList<>();
        for (Integer i : A) {
            list.add(i);
        }
        for (int i=0; i<B.length; i++){
            A[i] = findMin(list,B[i]);
        }
        for(int j=0; j<A.length; j++){
            if(A[j] == 0){
                A[j] = list.get(0);
                list.remove(0);
            }
        }
        return A;
    }
    private int findMin(List<Integer> list, int x) {
        for (Integer integer : list) {
            if (integer > x) {
                list.remove(integer);
                return integer;

            }
        }
        return 0;
    }

    /**
     * //给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
     * // '?' 可以匹配任何单个字符。
     * //'*' 可以匹配任意字符串（包括空字符串）。
     * // 两个字符串完全匹配才算匹配成功。
     * //
     * // 说明:
     * // s 可能为空，且只包含从 a-z 的小写字母。
     * // p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
     * //
     * // 示例 1:
     * // 输入:
     * //s = "aa"
     * //p = "a"
     * //输出: false
     * //解释: "a" 无法匹配 "aa" 整个字符串。
     * //
     * // 示例 2:
     * // 输入:
     * //s = "aa"
     * //p = "*"
     * //输出: true
     * //解释: '*' 可以匹配任意字符串。
     * //
     * // 示例 3:
     * // 输入:
     * //s = "cb"
     * //p = "?a"
     * //输出: false
     * //解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
     * //
     * // 示例 4:
     * // 输入:
     * //s = "adceb"
     * //p = "*a*b"
     * //输出: true
     * //解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
     * //
     * // 示例 5:
     * // 输入:
     * //s = "acdcb"
     * //p = "a*c?b"
     * //输出: false
     * // Related Topics 贪心算法 字符串 动态规划 回溯算法
     */
    public static boolean isMatch(String s, String p) {
        // 字符串s的索引
        int i = 0;
        // 匹配规则p的索引
        int j = 0;
        // s长度
        int m = s.length();
        // p长度
        int n = p.length();
        // 标记* 在s中的位置
        int iStart = -1;
        // 标记* 在p中的位置
        int jStart = -1;
        while (i < m){
            if (j < n && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')){
                // /i，j向后移
                i ++;
                j ++;
            }else if (j < n && p.charAt(j) == '*'){
                //记录出现 * 号时，i，j的位置
                iStart = i;
                jStart = j;
                j ++;
            }else if (iStart >= 0){
                i = ++ iStart;
                j = jStart + 1;

            }else {
                return false;
            }
        }
        while (j < n && p.charAt(j) == '*') ++j;//去除多余星号
        return j == n;
    }

    /**
     * //给定一个非负整数数组，你最初位于数组的第一个位置。
     * //
     * // 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * //
     * // 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     * //
     * // 示例:
     * //
     * // 输入: [2,3,1,1,4]
     * //输出: 2
     * //解释: 跳到最后一个位置的最小跳跃数是 2。
     * //     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     * //
     * //
     * // 说明:
     * //
     * // 假设你总是可以到达数组的最后一个位置。
     * // Related Topics 贪心算法 数组
     */
    public int jump(int[] nums) {
        int len = nums.length - 1;
        // 步数
        int res = 0;
        // 循环数组
        while (len > 0){
            // 找到最后一步到达最后位置的索引，并且索引最小的那个
            for (int i = 0; i < len; i ++){
                if (i + nums[i] >= len){
                    len = i;
                    res ++;
                    // 结束当前for循环，重新进入while循环，将最后位置设置为当前i的位置
                    break;
                }
            }
        }
        return res;
    }
    public static int jump1(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    /**
     * 给你一个非空的字符串 s 和一个整数 k，你要将这个字符串中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离至少为 k。
     *
     *  所有输入的字符串都由小写字母组成，如果找不到距离至少为 k 的重排结果，请返回一个空字符串 ""。
     *
     *  示例 1：
     *
     *  输入: s = "aabbcc", k = 3
     * 输出: "abcabc"
     * 解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。
     *
     *
     *  示例 2:
     *
     *  输入: s = "aaabc", k = 3
     * 输出: ""
     * 解释: 没有办法找到可能的重排结果。
     *
     *
     *  示例 3:
     *
     *  输入: s = "aaadbbcc", k = 2
     * 输出: "abacabcd"
     * 解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。
     *
     *  Related Topics 堆 贪心算法 哈希表
     *
     * TODO 解题思路
     * 先统计所有字符出现的次数，存入一个 HashMap 中，接着按照重复次数 (char,count) 从大到小构建一个大顶堆，把 map 中的元素装入大顶堆中。
     *
     * 创建一个 StringBuilder 对象 sb。
     * 创建一个普通队列变量 queue 同步记录已经加入到 sb 中的字符。
     *
     * 循环遍历大顶堆的字符：
     * 1、取出一个字符 c ，把它加入到 sb 中；
     * 2、把 c 的重复次数减一，加入到一个普通队列 queue 中；
     * 3、判断 queue 中的元素个数是否为 k，如果是，说明 sb 中距离上一个字符 c 已经插入了 k 个字符了，
     * 现在字符 c 可以再出现一次了，把 queue 队首元素放入大顶堆。
     *
     * 当大顶堆没有元素了：
     * 1、sb 的长度和 s 一样，说明重构完成，返回 sb.toString();
     * 2、sb 的长度和 s 不一样，说明还有些字符挂在 queue 中，没有装入大顶堆，说明有些字符无法间隔 k 个距离。
     *
     */
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        // hashMap 集合
        HashMap<Character, Integer> hashMap = new HashMap<>();
        // 大顶堆
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(
                (a, b) -> b.getValue() - a.getValue()
        );
        for (Character character : s.toCharArray()){
            // hashMap 中是否存在character
            // TODO getOrDefault : 当Map集合中有这个key时，就使用这个key对应的value值，如果没有就使用默认值defaultValue
            hashMap.put(character, hashMap.getOrDefault(character, 0) + 1);
        }
        // TODO entrySet : map中各个键值对映射关系的集合
        // 将map中的映射关系集合放入大顶堆中
        maxHeap.addAll(hashMap.entrySet());
        // 动态拼接字符串
        StringBuilder stringBuilder = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
        while (!maxHeap.isEmpty()){
            // 根据次数，依次取出
            Map.Entry<Character, Integer> mapEntry = maxHeap.poll();
            // 字符串追加
            stringBuilder.append(mapEntry.getKey());
            // 该字符串频率减去1
            mapEntry.setValue(mapEntry.getValue() - 1);
            // 向对列中加入该map,当到达k后再进行出队列
            queue.add(mapEntry);
            if (queue.size() == k){
                // 队列中元素依次出队列
                Map.Entry<Character, Integer> entry = queue.poll();
                if (entry.getValue() > 0){
                    // 该字符的重复次数大于 0，则再次添加入大顶堆中
                    maxHeap.add(entry);
                }
            }
        }
        // 当大顶堆中没有元素后，如果stringBuilder与初始字符串长度不一致，说明还有元素在对列里边
        return stringBuilder.length() == s.length() ? stringBuilder.toString() : "";
    }

    /**
     * 给定两个正整数数组 boxes 和 warehouse ，分别包含单位宽度的箱子的高度，以及仓库中 n 个房间各自的高度。仓库的房间分别从 0 到 n -
     * 1 自左向右编号， warehouse[i] （索引从 0 开始）是第 i 个房间的高度。
     *
     *  箱子放进仓库时遵循下列规则：
     *  箱子不可叠放。
     *  你可以重新调整箱子的顺序。
     *  箱子只能从左向右推进仓库中。
     *  如果仓库中某房间的高度小于某箱子的高度，则这个箱子和之后的箱子都会停在这个房间的前面。
     *  你最多可以在仓库中放进多少个箱子？
     *  示例 1：
     * 输入：boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
     * 输出：3
     * 解释：
     *
     * 我们可以先把高度为 1 的箱子放入 4 号房间，然后再把高度为 3 的箱子放入 1 号、 2 号或 3 号房间，最后再把高度为 4 的箱子放入 0 号房间。
     *
     * 我们不可能把所有 4 个箱子全部放进仓库里。
     *
     *  示例 2：
     * 输入：boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
     * 输出：3
     * 解释：
     *
     * 我们注意到，不可能把高度为 4 的箱子放入仓库中，因为它不能通过高度为 3 的房间。
     * 而且，对于最后两个房间 2 号和 3 号来说，只有高度为 1 的箱子可以放进去。
     * 我们最多可以放进 3 个箱子，如上图所示。黄色的箱子也可以放入 2 号房间。
     * 交换橙色和绿色箱子的位置，或是将这两个箱子与红色箱子交换位置，也是可以的。
     *
     *  示例 3：
     * 输入：boxes = [1,2,3], warehouse = [1,2,3,4]
     * 输出：1
     * 解释：由于第一个房间的高度为 1，我们只能放进高度为 1 的箱子。
     *
     *  示例 4：
     * 输入：boxes = [4,5,6], warehouse = [3,3,3,3,3]
     * 输出：0
     *
     *  提示：
     *  n == warehouse.length
     *  1 <= boxes.length, warehouse.length <= 10^5
     *  1 <= boxes[i], warehouse[i] <= 10^9
     *
     *  Related Topics 贪心算法
     *
     *  TODO 思路：
     *  1.遍历 warehouse（仓库），不断更新到目前位置为止的最小值（不然会卡在前面进不来）。
     *  2.对 boxes（箱子） 排序，从最矮的开始放才能放进最多个。
     *  3.模拟推箱子，记录答案。
     *
     *
     */
    public static int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {

        // 保证仓库呈梯度下降数组，第一个位置决定仓库箱子的最大高度，进行梯度获取最小值
        for (int i = 1; i < warehouse.length; i ++){
            warehouse[i] = Math.min(warehouse[i], warehouse[i - 1]);
        }
        // 将箱子进行从小到大进行排序
        Arrays.sort(boxes);
        int box = 0;
        // 仓库高度从高到低进行排列，箱子高度从低到高
        for (int i = warehouse.length - 1, j = 0; i >= 0 && j < boxes.length; i --){
            if (warehouse[i] >= boxes[j]){
                // 箱子个数++
                j ++;
                box ++;
            }
        }
//        Arrays.sort(boxes,new Comparator<Integer>(){
//            public int compare(Integer o1, Integer o2) {
//                return o1 - o2;
//            }
//        });
        return box;
    }






    public static void main(String[] args) {
//        String s = "acdcb";
//        String p = "a*c?b";
//        isMatch(s, p);
//        int[] ints = {2,3,1,1,4};
//        int step = jump1(ints);

        int[] ints = {4,3,4,1};
        int[] int2 = {5,3,3,4,1};
        int box = maxBoxesInWarehouse(ints, int2);
        System.out.println("==============");
    }
}
